#ifndef SOLUTION_H_
#define SOLUTION_H_
#ifndef NULL
#define NULL 0
#endif

struct ListNode 
{
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
};
class Solution
{
public:
	ListNode *reverseBetween(ListNode *head, int m, int n) 
	{
		// Start typing your C/C++ solution below
		// DO NOT write int main() function

		if(!head)
			return head;
		ListNode *pre = NULL, *first = head;
		for(int i=1;i<m;i++)
		{
			pre = first;
			first = first->next;
		}

		ListNode *second = first;
		for(int i=m;i<n;i++)
			second = second->next;

		ListNode* behind = second->next;

		ListNode* tpre = pre, *ts = first->next, *tcur = first;
		while(tcur!=behind)
		{
			ts = tcur->next;
			tcur->next = tpre;
			tpre = tcur;
			tcur = ts;
		}

		if(pre)
			pre->next = second;
		else
			head = second;

		first->next = behind;

		return head;
	}
};
#endif